package demo1;

import java.util.*;

public class TreeBinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode root;//二叉树的根节点

    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = H;
        C.left = F;
        C.right = G;
        //返回这颗树的根节点
        return A;

    }

    //前序遍历 根 左子树 右子树 递归
    public void preOrder(TreeNode root){
        if (root == null){
            return ;
        }
        System.out.print(root.val + " ");

        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历
    public void inOrder(TreeNode root) {
        if (root == null){
            return ;
        }
        preOrder(root.left);
        System.out.print(root.val + " ");
        preOrder(root.right);
    }

    //后序遍历
    public void postOrder(TreeNode root) {
        if (root == null){
            return ;
        }
        preOrder(root.left);
        preOrder(root.right);
        System.out.print(root.val + " ");
    }
    //获取节点的个数
    int treeSize = 0;
    public int size(TreeNode root){
        if (root == null){
            return  0;
        }
        treeSize++;
        size(root.left);
        size(root.right);
        return treeSize;
    }

    // 获取叶子节点的个数
    public  int getLeafNodeCount(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right ==null){
            return 1;
        }
        int leftnum = getLeafNodeCount(root.left);
        int rightnum = getLeafNodeCount(root.right);

        return leftnum+rightnum;
    }



    /*
    * 时间复杂度 ：O(n)
    * 空间复杂度 ：树的高度
    *
    */
   public int maxDepth(TreeNode root) {
       if(root == null){
           return 0;
       }
       int leftHight = maxDepth(root.left);
       int rightHight = maxDepth(root.right);

       int num = leftHight>rightHight ? leftHight:rightHight;

       return num+1;
   }

   //获取第K层节点的个数
   public int getKLevelNodeCount(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        int leftSize = getKLevelNodeCount(root.left,k-1);
       int rightSize = getKLevelNodeCount(root.right,k-1);

       return leftSize+rightSize;

   }
   //检测值为value 的元素是否存在？
   public TreeNode find(TreeNode root,int val) {
       if (root == null) {
           return null;
       }

       if (root.val == val) {
           return root;
       }

       TreeNode leftTree = find(root.left,val);
       if(leftTree!=null){
           return leftTree;
       }
       TreeNode rightTree = find(root.right,val);
       if(rightTree!=null){
           return rightTree;
       }

        return null;//没有找到
   }

   //相同的树
   //时间复杂度 O(min(p,q))
   //空间复杂度 O(min(p,q))
   public boolean isSameTree(TreeNode p, TreeNode q) {
       if(p ==null && q!=null || p!=null && q==null ){
           return false;
       }
       if(p == null && q== null){
           return true;
       }

       if(p.val != q.val){
           return false;
       }
       return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
   }

   //另一棵树的子树
    /*
    *1. 是不是相同的树
    * 2. 是不是root的左子树
    * 3. 是不是root的右子树
    * */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {

       //在比较中，如果有一方是null 直接返回 false
       if(root == null || subRoot == null){
           return false;
       }
       if(isSameTree(root,subRoot)){
           return true;
       }
       if(isSubtree(root.left,subRoot)){
           return true;
       }
       if(isSubtree(root.right,subRoot)){
           return true;
       }
       return false;

    }
    //翻转二叉树
    /*
    *交换root的左 和 root的右
    * 再交换root左树的 左和右
    * 最后交换root 右树的 左和右
    * */
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }

    //平衡二叉树
    /*
    * 左右高度差 不超过 1
    * 时间复杂度 ：n*n
    * 空间复杂度 ：
    * */
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int leftHight = maxDepth(root.left);
        int rightHight = maxDepth(root.right);

        return Math.abs(leftHight-rightHight) < 2
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

    //O(n) 实现
    /*
    * 求高度的过程中 就判断 是否平衡？
    * */
    public boolean isBalanced2(TreeNode root) {
        return maxDepth2(root) >=0;

    }
    public int maxDepth2(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftHight = maxDepth2(root.left);
        if(leftHight < 0) return -1;
        int rightHight = maxDepth2(root.right);
        if(rightHight < 0) return -1;

        if(Math.abs(leftHight-rightHight)<=1){
            return Math.max(leftHight,rightHight)+1;
        }else{
            return -1;
        }
    }
    //对称二叉树
    /*
    * root 左节点和右键点是否相同
    *左子树的左树 和 右子树的右树
    * 左子树的右树 和 右子树的左树
    * */
    public boolean isSymmetric(TreeNode root) {
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        //左节点为空 右节点不为空
        //左节点不为空 右节点为空
        if(leftTree == null && rightTree != null || leftTree != null  && rightTree == null){
            return false;
        }

        if(leftTree == null || rightTree == null){
            return true;
        }

        if(leftTree.val != rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);

    }

    //二叉树的层序遍历
    public  void levelOrder(TreeNode root){
        if(root == null){
            return ;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }

    }

    //层序遍历
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        if(root == null) return ret;
        Queue<TreeNode> queue  = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new LinkedList<>();
            while(size!=0){
                TreeNode cur = queue.poll();
               /*oj能跑*/  // list.add(cur.val);
                --size;
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }

            }
            ret.add(list);
        }
        return ret;
    }


    //

    public boolean getPath(TreeNode root, TreeNode node,
                           Deque<TreeNode> stack) {
        if(root == null || node == null)return false;
        stack.push(root);
//放完之后 要检查
        if(root == node) return true;
        boolean ret1 = getPath(root.left,node,stack);
        if(ret1) return true;
        boolean ret2 = getPath(root.right,node,stack);
        if(ret2) return true;
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
//1、两个栈当中 存储好数据
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(root,p,stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,q,stack2);
//2、判断栈的大小
        int len = stack1.size() - stack2.size();
        if(len> 0){
            while(len-- >0){
                stack1.pop();
            }
        }else {
            len = -len;
            while (len-- >0){
                stack2.pop();
            }
        }


        while(!stack1.isEmpty() && !stack2.isEmpty()){
            //因为拿的是 地址 可以判断！
            //先看看 再弄。。。
            if(stack1.peek() == stack2.peek()){
                return stack1.peek();
            }else{
                stack1.pop();
                stack2.pop();
            }
        }
        return null;

    }

    public int i = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }

    public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin,int inend) {
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[i]);
//找到当前根，在中序遍历的位置
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[i]);
        i++;
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }

    private int findIndex( int[] inorder,int inbegin,int end, int key) {
        for (int j = inbegin; j <=end ; j++) {
            if(inorder[i] == key) return i;
        }
        return -1;
    }


    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root){
        if(root == null){
            return true;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
           TreeNode cur =  queue.poll();
           if(cur != null){
               queue.offer(cur.left);
               queue.offer(cur.right);
           }else{
               break;
           }
        }
        while(!queue.isEmpty()){
            TreeNode tmp = queue.poll();
            if(tmp != null){
                return false;
            }
        }
        return true;



    }



}
